package cn.njupt.tree;

import cn.njupt.printer.BinaryTreeInfo;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree<E> implements BinaryTreeInfo {

    protected int size;

    protected Node<E> root;

    protected static class Node<E> {
         E element;
         Node<E> left;
         Node<E> right;
         Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public boolean hasTwoChildren(){
            return left!=null && right!=null;
        }

        public boolean isLeftChild(){
            return parent!=null && this==parent.left;
        }
        public boolean isRightChild(){
            return parent!=null && this==parent.right;
        }

    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node) node).right;
    }

    @Override
    public Object string(Object node) {
        return  node;
    }


    /**
     * 创建节点
     * @param element
     * @param parent
     * @return
     */
    protected Node<E> createNode(E element,Node<E> parent){
        return new Node<>(element,parent);
    }

    public Node<E> getRoot(){
        return root;
    }

    public void clear() {
        root=null;
        size=0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    /**
     * 判断是否是一颗完全二叉树
     *
     * @param root
     * @return
     */
    public boolean isComplete(Node<E> root) {
        if (root == null) return false;
        boolean leaf = false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node<E> curNode = queue.poll();
            Node<E> left = curNode.left;
            Node<E> right = curNode.right;
            if (leaf && (left != null || right != null)
                    || (left == null && right != null)) {
                return false;
            }
            if (left != null) {
                queue.add(left);
            }
            if (right != null) {
                queue.add(right);
            } else {
                leaf = true;
            }
        }
        return true;

    }

    /**
     * 得到某个节点的前驱节点
     * @param node
     * @return
     */
    protected Node<E> getPreceNode(Node<E> node){
        if(node==null)return node;
        if(node.left!=null){
            return getRightNode(node.left);
        }else{
            Node<E> parent=node.parent;
            while(parent!=null && parent.right!=node){
                node=parent;
                parent=node.parent;
            }
            return parent;
        }
    }

    protected Node<E> getRightNode(Node<E> node){
        while(node.right!=null){
            node=node.right;
        }
        return node;
    }

    /**
     * 前序遍历二叉树,访问者模式？
     */
    public void preOrderTraversal(Node<E> root, Visitor<E> visitor){
        if(root==null || visitor.stop)return;

        //访问者模式，让二叉树遍历遍历到什么节点停止
        if(visitor.stop)return ;

        visitor.stop=visitor.visit(root.element);

        preOrderTraversal(root.left,visitor);
        preOrderTraversal(root.right,visitor);

    }

    /**
     * 中序遍历二叉树
     */
    public void inOrderTraversal(Node<E> root){
        if(root==null)return;
        inOrderTraversal(root.left);
        System.out.println(root.element);
        inOrderTraversal(root.right);
    }

    /**
     * 后序遍历二叉树
     */
    public void postOrderTraversal(Node<E> root){
        if(root==null)return;
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.println(root.element);
    }

    /**
     * 层序遍历二叉树
     */
    public void levelOrderTraversal(Node<E> root){
        if(root==null)return;
        Queue<Node<E>> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            Node<E> curNode=queue.poll();
            System.out.println(curNode.element);
            if(curNode.left!=null){
                queue.offer(curNode.left);
            }
            if(curNode.right!=null){
                queue.offer(curNode.right);
            }
        }

    }

    /**
     * 非递归二叉树前序遍历
     */
    public void preTraversalByStack(){
        Node<E> node=root;
        Stack<Node> stack=new Stack<>();
        while(true){
            if(node!=null){
                System.out.println(node.element);
                if(node.right!=null){
                    stack.push(node.right);
                }
                node=node.left;
            }else{
                if(stack.isEmpty()){
                    return;
                }
                node=stack.pop();
            }
        }
    }

    /**
     * 非递归二叉树中序遍历
     */
    public void inTraversalByStack(){
        Node<E> node=root;
        Stack<Node> stack=new Stack<>();
        while(true){
            if(node!=null){
                stack.push(node);
                node=node.left;
            }else{
                if(stack.isEmpty())return;
                node=stack.pop();
                System.out.println(node.element);
                node=node.right;
            }
        }
    }

    /**
     * 非递归二叉树后序遍历
     */
    public void postTraversalByStack(){
        Node<E> node=root;
        Stack<Node> stack=new Stack<>();
        stack.push(root);
        Node<E> prev=null;
        while(!stack.isEmpty()){
            Node<E> cur=stack.peek();
            if((cur.left==null && cur.right==null) || (prev!=null && prev.parent==cur)){
                prev=stack.pop();
                System.out.println(prev.element);
            }else{
                if(cur.right!=null){
                    stack.push(cur.right);
                }
                if(cur.left!=null){
                    stack.push(cur.left);
                }
            }
        }
    }

    @Override
    public String toString() {
        return "BinaryTree{" +
                "size=" + size +
                ", root=" + root +
                '}';
    }

    public abstract class Visitor<E> {
        boolean stop;
        public abstract boolean visit(E element);
    }

}
